package com.wang.sort2;

/**
 * @Author: along
 * @Create: 2021/4/14 11:56
 * @Description:复杂链表的复制(多了一个随机指针指向其他节点或空)
 */
import java.util.HashMap;

    public class Demo03_CopyListWithRandom {

        public static class Node {
            public int value;
            public Node next;
            public Node rand;

            public Node(int data) {
                this.value = data;
            }
        }
        //哈希表 空间和时间都是O(n)
        public static Node copyListWithRand1(Node head) {
            //map中存的是(原节点，拷贝节点)的一个映射
            HashMap<Node, Node> map = new HashMap<Node, Node>();
            Node cur = head;
            while (cur != null) {
                map.put(cur, new Node(cur.value));
                cur = cur.next;
            }
            cur = head;
            while (cur != null) {
                // cur 老
                // map.get(cur) 新
                map.get(cur).next = map.get(cur.next);
                map.get(cur).rand = map.get(cur.rand);
                cur = cur.next;
            }
            return map.get(head);
        }
        //原地修改 空间复杂度为O(1)
        public static Node copyListWithRand2(Node head) {
            if (head == null) {
                return null;
            }
            Node cur = head;
            Node next = null;
            // copy node and link to every node
            // 1 -> 2
            // 1 -> 1' -> 2
            while (cur != null) {
                // cur 老
                next = cur.next;
                cur.next = new Node(cur.value);
                cur.next.next = next;
                cur = next;
            }
            cur = head;
            Node curCopy = null;
            // set copy node rand
            // 1 -> 1' -> 2 -> 2'
            while (cur != null) {
                // cur 老
                // cur.next  新 copy
                next = cur.next.next;
                curCopy = cur.next;
                curCopy.rand = cur.rand != null ? cur.rand.next : null;
                cur = next;
            }
            Node res = head.next;
            cur = head;
            // split
            while (cur != null) {
                next = cur.next.next;
                curCopy = cur.next;
                cur.next = next;
                curCopy.next = next != null ? next.next : null;
                cur = next;
            }
            return res;
        }

        public static void printRandLinkedList(Node head) {
            Node cur = head;
            System.out.print("order: ");
            while (cur != null) {
                System.out.print(cur.value + " ");
                cur = cur.next;
            }
            System.out.println();
            cur = head;
            System.out.print("rand:  ");
            while (cur != null) {
                System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
                cur = cur.next;
            }
            System.out.println();
        }

        public static void main(String[] args) {
            Node head = null;
            Node res1 = null;
            Node res2 = null;
            printRandLinkedList(head);
            res1 = copyListWithRand1(head);
            printRandLinkedList(res1);
            res2 = copyListWithRand2(head);
            printRandLinkedList(res2);
            printRandLinkedList(head);
            System.out.println("=========================");

            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(3);
            head.next.next.next = new Node(4);
            head.next.next.next.next = new Node(5);
            head.next.next.next.next.next = new Node(6);

            head.rand = head.next.next.next.next.next; // 1 -> 6
            head.next.rand = head.next.next.next.next.next; // 2 -> 6
            head.next.next.rand = head.next.next.next.next; // 3 -> 5
            head.next.next.next.rand = head.next.next; // 4 -> 3
            head.next.next.next.next.rand = null; // 5 -> null
            head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4

            printRandLinkedList(head);
            res1 = copyListWithRand1(head);
            printRandLinkedList(res1);
            res2 = copyListWithRand2(head);
            printRandLinkedList(res2);
            printRandLinkedList(head);
            System.out.println("=========================");

        }
    }
